'''
最长公共子序列
    一个序列的子序列是在该序列中删去若干元素后得到的序列.

    最长公共子序列问题(LCS):给定两个序列X和Y,求X和Y长度最大的公共子序列
        例:X='ABBCBDE' Y='DBBCDB' LCS(X,Y) = 'BBCD'

    应用场景:字符串相似度对比

    定理(LCS的最优子结构): 令X = [x1,x2,...,xm] 和Y = [y1,y2,...,yn]为两个序列,
    Z = [z1,z2,...,zk]为X和Y的任意LCS.
        1.如果xm = yn,则 zk = xm = yn 且Zk-1是Xm-1和Yn-1的一个LCS.
        2.如果xm != yn,则 zk != xm 意味着Z是Xm-1和Y的一个LCS.
        3.如果xm != yn,则 zk != yn 意味着Z是X和Yn-1的一个LCS.

    最优解的递推式
                  0                         若i = 0 或 j = 0
        c[i,j] =  c[i-1,j-1]+1              若i,j > 0,且xi = yj
                  max(c[i,j-1],c[i-1,j])    若i,j > 0,且xi != yj

        c[i,j]表示Xi和Yj的LCS长度
'''
def lcs_length(x,y):
    m = len(x)
    n = len(y)
    c = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1,m+1):
        for j in range(1,n+1):
            if x[i-1] == y[j-1]:  # x,y是字符串,不是二维列表的行和列
                c[i][j] = c[i-1][j-1] + 1
            else:
                c[i][j] = max(c[i-1][j],c[i][j-1])
    for _ in c:
        print(_)
    return c[m][n]

def lcs(x,y):
    m = len(x)
    n = len(y)
    c = [[0]*(n+1) for _ in range(m+1)]
    b = [[0]*(n+1) for _ in range(m+1)] # 1 左上方, 2 上方, 3 左方
    for i in range(1,m+1):
        for j in range(1,n+1):
            if x[i-1] == y[j-1]:  # x,y是字符串,不是二维列表的行和列
                c[i][j] = c[i-1][j-1] + 1
                b[i][j] = 1
            else:
                if c[i-1][j] > c[i][j-1]:
                    c[i][j] = c[i-1][j]
                    b[i][j] = 2
                elif c[i-1][j] < c[i][j-1]:
                    c[i][j] = c[i][j-1]
                    b[i][j] = 3
    for _ in c:
        print(_)
    print('===============')
    for _ in b:
        print(_)
    return c[m][n],b

def lcs_traceback(x,y):
    c,b = lcs(x,y)
    i = len(x)
    j = len(y)
    res = []
    while i > 0 and j > 0:
        if b[i][j] == 1: #来自左上方,匹配
            res.append(x[i-1])
            i -= 1
            j -= 1
        elif b[i][j] == 2: # 来自于上方,不匹配
            i -= 1
        else:              # 来自左方,不匹配
            j -= 1
    res.reverse()
    return ''.join(res)
X = 'ABCBDAB'
Y = 'BDCABA'
print(lcs(X,Y))
print(lcs_traceback(X,Y))